class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void dfs(vector<int>& candidates, int target,int cur,int sum){
        if(sum==target){
            res.emplace_back(tmp);
            return;
        }
        else if(sum>target){
            return;
        }
        for(int i=cur;i<candidates.size();i++){
            tmp.push_back(candidates[i]);
            sum+=candidates[i];
            dfs(candidates,target,i,sum);
            tmp.pop_back();
            sum-=candidates[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }
};
